package com.hyc.DataStructure.sort;

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.sort
 * @className: shellSort
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/1/13 22:37
 * @version: 1.0
 */
public class shellSort {

    public static void main(String[] args) {
        int[] nums = {3, 5, 1, 6, 0, 8, 9, 4, 7, 2};
        int[] test = new int[80000];
        //测试数据
        for (int i = 0; i < 80000; i++) {
            test[i] = (int) (Math.random() * 80000);
        }
        long time = System.currentTimeMillis();
        shellsortByinsert(test);
        long end = System.currentTimeMillis();
        long t = ((end - time) / 1000);
        System.out.println("一共用时 " + t + "秒");
    }

    public static void shellsort(int[] nums) {
        int temp = 0;
        int count = 0;
        //这里设置分组区间 每次将数组除以二 之后的商为数组分组的数量
        for (int gap = nums.length / 2; gap > 0; gap /= 2) {
            //遍历数组内的所有的元素一共（gap组 每组里），步长 gap
            for (int i = gap; i < nums.length; i++) {
                //当前元素大于步长gap的说明在一组 判断大小交换
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (nums[j] > nums[j + gap]) {
                        temp = nums[j];
                        nums[j] = nums[j + gap];
                        nums[gap + j] = temp;
                    }
                }
            }
            //System.out.println("希尔排序第" + (++count) + "轮=" + numsays.toString(nums));
        }
    }

    //用插入排序 来实现希尔分组后的交换位置（优化）
    public static void shellsortByinsert(int[] nums) {
        for (int gap = nums.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < nums.length; i++) {
                //存放当前下标
                int j = i;
                //存放当前下标数组内的值
                int temp = nums[j];
                if (nums[j] < nums[j - gap]) {
                    while (j - gap >= 0 && temp < nums[j - gap]) {
                        nums[j] = nums[j - gap];
                        j -= gap;
                    }
                    nums[j] = temp;
                }

            }
        }
    }

}
